package TreeSerialize;

import offer.TreeNode;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @Auther: wangliuyang
 * @Date: 2021/4/27 22:17
 * @Description:
 */
public class LevelSerialize {
    private final String NULL = "null";
    private final String SPLIT = ",";
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        if (root == null){
            sb.append(NULL);
            return sb.toString();
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node == null) {
                    sb.append(NULL).append(SPLIT);
                }else {
                    sb.append(String.valueOf(node.val)).append(SPLIT);
                    queue.add(node.left);
                    queue.add(node.right);
                }
            }
        }
        return sb.substring(0,sb.length()-1).toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] datas = data.split(SPLIT);
        Queue<String> nodes = new LinkedList<>(Arrays.asList(datas));
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode root = generateNode(nodes.poll());
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node == null) {
                    continue;       //空节点不需要构建左右子树
                }
                node.left = generateNode(nodes.poll());
                queue.add(node.left);
                node.right = generateNode(nodes.poll());
                queue.add(node.right);
            }
        }
        return root;
    }

    public TreeNode generateNode(String val) {
        if (val.equals(NULL)) {
            return null;
        }
        return new TreeNode(Integer.valueOf(val));
    }
}
